package com.dq.offer;

import java.util.PriorityQueue;

/**
 * @Author: Dang Qi
 * @Date: 2021/3/15  12:50
 * @Description:
 */
class MedianFinder {
    public static void main(String[] args) {
        MedianFinder finder = new MedianFinder();
        finder.addNum(1);
        finder.addNum(2);
        System.out.println(finder.findMedian());
        finder.addNum(3);
        System.out.println(finder.findMedian());
    }
    private PriorityQueue<Integer> maxHeap = null;
    private PriorityQueue<Integer> minHeap = null;
    /** initialize your data structure here. */
    public MedianFinder() {
        maxHeap = new PriorityQueue<>((a,b) -> b-a);
        minHeap = new PriorityQueue<>();
    }

    public void addNum(int num) {

        if(maxHeap.size()==0) maxHeap.offer(num);
        else if(maxHeap.size() == minHeap.size()){
            minHeap.offer(num);
            maxHeap.offer(minHeap.poll());
        }else if(maxHeap.size() > minHeap.size()){
            maxHeap.offer(num);
            minHeap.offer(maxHeap.poll());
        }
    }

    public double findMedian() {
        if(maxHeap.size()!=0) {
            if(maxHeap.size() == minHeap.size())
                return (maxHeap.peek() + minHeap.size()) / 2;
            else return maxHeap.peek();
        }
        return -1;
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */
